#include <bits/stdc++.h>
#define maxsize 50
using namespace std;
/* 
一棵完全二叉树存储于顺序表s中，s.elem[1...s.last]，
编写算法建立二叉树的二叉链表
 */
// 顺序表
typedef struct sqlist
{
    int data[maxsize] = {};
    int length = 0;
} slist;
// 二叉树的二叉链表
typedef struct binode
{
    int data;
    struct binode *lchild;
    struct binode *rchild;
} binode, *bitree;
// 创建元素下标从1开始的顺序表
void createlist(slist &l)
{
    int x;
    int i = 1;
    cout << "输入元素，回车键结束" << endl;
    cin >> x;
    while (x != 999)
    {
        l.data[i] = x;
        i++;
        l.length++;
        cout << "输入元素，999结束" << endl;
        cin >> x;
    }
}
void printlist(slist l)
{
    for (int i = 0; i < l.length; i++)
    {
        cout << l.data[i + 1] << " ";
    }
    cout << endl;
}
// 将顺序表中的完全二叉树转存到二叉链表中
//主函数中传入的i为1
void CreateTree(slist l, bitree &t, int i) //前序创建
{
    t = (bitree)malloc(sizeof(binode)); //分配空间
    t->data = l.data[i];
    if (l.length >= 2 * i) //若长度大于2i，证明此节点有左子树
        CreateTree(l, t->lchild, 2 * i);
    else
    {
        t->lchild = NULL;
    }
    if (l.length >= 2 * i + 1) //若长度大于2i+1，证明此节点有右子树
        CreateTree(l, t->rchild, 2 * i + 1);
    else
    {
        t->rchild = NULL;
    }
}
void preorder(bitree t)
{

    if (t != NULL)
    {
        cout << t->data << " ";
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
void inorder(bitree t)
{

    if (t != NULL)
    {
        inorder(t->lchild);
        cout << t->data << " ";
        inorder(t->rchild);
    }
}
int main(int argc, char const *argv[])
{
    slist l;
    bitree t;
    createlist(l);
    cout << "顺序表" << endl;
    printlist(l);
    CreateTree(l, t, 1);
    cout << "先序遍历" << endl;
    preorder(t);
    cout << endl;
    cout << "中序遍历" << endl;
    inorder(t);
    system("pause");
    return 0;
}
